package com.algorithm.ch1.cjm.tree;

import com.algorithm.ch1.cjm.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树的层次遍历
 * 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
 * <p>
 * 例如:
 * 给定二叉树: [3,9,20,null,null,15,7],
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回其层次遍历结果：
 * <p>
 * [
 * [3],
 * [9,20],
 * [15,7]
 * ]
 */
public class LevelOrder {

    /**
     * 第一版
     * 一层层的求出不同深度的节点数目
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {

        if(root == null){
            return new ArrayList<>();
        }

        int depth = 1;
        List<List<Integer>> allNode = new ArrayList<>();

        List<TreeNode> depthNode = null;
        while (true){
            depthNode = getNodeByDepth(root, depth);
            if(depthNode.size() == 0) {
                break;
            }
            depth++;

            allNode.add(transInteger(depthNode));
        }
        return allNode;
    }

    /**
     * 对应的节点值转换为integer
     * @param list
     * @return
     */
    List<Integer> transInteger(List<TreeNode> list){

        List<Integer> list1 = new ArrayList<>();

        for (TreeNode node : list){
            list1.add(node.val);
        }

        return list1;
    }

    /**
     * 获取当前深度的所有节点数
     * @param root
     * @param depth
     * @return
     */
    List<TreeNode> getNodeByDepth(TreeNode root,int depth){

        List<TreeNode> list = new ArrayList<>();

        if(depth == 1){

            list.add(root);

            return list;
        }

        List<TreeNode> preList = getNodeByDepth(root,  --depth);

        for (TreeNode node : preList){

            if(node.left != null) {
                list.add(node.left);
            }
            if(node.right != null) {
                list.add(node.right);
            }
        }

        return list;
    }


    /**
     * leetcode 最优解
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        set(root, 0, result);
        return result;
    }

    public void set(TreeNode treeNode, int level, List<List<Integer>> result) {
        if(treeNode==null){
            return;
        }
        if(level==result.size()){
            result.add(new ArrayList<Integer>());
        }
        result.get(level).add(treeNode.val);
        set(treeNode.left,level+1,result);
        set(treeNode.right,level+1,result);
    }

}
